DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2018.8

The Amortized Analysis of a Non-blocking Chromatic Tree

Authors: Jeremy Ko

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract

A non-blocking chromatic tree is a type of balanced binary search tree where multiple processes can concurrently perform search and update operations. We prove that a certain implementation has amortized cost O(dot{c} + log n) for each operation, where dot{c} is the maximum number of concurrent operations at any point during the execution and n is the maximum number of keys in the tree during the operation. This amortized analysis presents new challenges compared to existing analyses of other non-blocking data structures.

Cite as

Jeremy Ko. The Amortized Analysis of a Non-blocking Chromatic Tree. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ko:LIPIcs.OPODIS.2018.8,
  author =	{Ko, Jeremy},
  title =	{{The Amortized Analysis of a Non-blocking Chromatic Tree}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.8},
  URN =		{urn:nbn:de:0030-drops-100688},
  doi =		{10.4230/LIPIcs.OPODIS.2018.8},
  annote =	{Keywords: amortized analysis, non-blocking, lock-free, balanced binary search trees}
}

Search Results

Documents authored by Ko, Jeremy

The Amortized Analysis of a Non-blocking Chromatic Tree

Abstract

Cite as

Thanks for your feedback!

Could not send message